在日常工作中，我们经常会用到遍历操作。如遍历一颗树，找到某个节点。遍历又分为广度优先遍历 (Depth First Search)和深度优先遍历(Breadth First Search)两种。
# 1、深度优先遍历(DFS)
首先访问根节点，其次是它的子节点，访问子节点的子节点，直到子节点没有子节点为止，就这样一直循环下去，直到根节点下所有的子节点都被访问到为止。简单点说就是，从根节点出发，按照从左到右的顺序，访问其子节点，如果子节点还有子节点，则一直向下访问，直到没有子节点为止。然后再返回到离根节点最近的而没有访问到的子节点，然后按照前面的查找方法，一遍一遍的循环下去，直到所有的节点被访问完毕为止。 算法实现如下：
function deepTranversal(node，nodeList=[]){
if(node){
nodeList.push(node)
let children=node.children;
let len=children.length;
if(children&&len){
for(let i=0;i<len;i++){
deepTranversal(node,nodeList)
}
}
}
return nodeList;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
//验证
<div id="A">
A
<div id="B1">
B1
<span id="C1">C1</span>
<span id="C2">C2</span>
</div>
<div id="B2">B2
<span id="C3">C3</span>
<span id="C4">C4</span>
</div>
<div id="B3">B3
<span id="C5">C5</span>
<span id="C6">C6</span>
</div>
<div id="B4">B4
<span id="C7">C7</span>
<span id="C8">C8</span>
</div>
</div>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
<!-- 如上所示节点树 -->
let node=document.querySelector("#A");
for(let item of deepTranversal(node,[])){
console.log(item.id);
}
1
2
3
4
5
6
2
3
4
5
6
输出结果如下
# 2、广度优先遍历
首先访问根节点，其次是它的子节点，然后按照从左到右的顺序，访问子节点的子节点，直到子节点没有子节点为止，就这样一直循环下去，直到根节点下所有的子节点都被访问到为止。简单点说就是从根节点出发，一层一层的从上向下访问，同层节点从左往右访问，直到所有的节点都被访问到为止。 算法实现如下：
function breadthTranversal(node,nodeList=[]){
let satck=[];
if(node){
stack.push(node);
while(stack.length){
let item=stack.shift();
nodeList.push(item);
let children=item.children;
let len=children.length;
for(let i=0;i<len;i++){
stack.push(children[i]);
}
}
}
return nodeList;
}
//验证 节点还是上面的节点数据
for(let item of breadthTranversal(node,[])){
console.log(item.id)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
输出结果如下